Regarding the Intermediate Values


(A) This folder contains the intermediate-value files for QR-UOV.
Each file contains the results and intermediate values generated using fixed test inputs for key generation, signature generation, and verification. These inputs include the private-key seed, message, salt, and y_input.

The NIST security levels I, III, and V correspond to the security parameter values lambda = 128, 192, and 256, respectively. For each parameter set, we define the number of vinegar variables v, the number of oil variables m, the degree l of the irreducible polynomial f defining the quotient ring GF(q)[x]/(f), and the prime power q.

Each parameter set has two files: one for the AES option and one for the SHAKE option. The files follow the naming convention:

    QR-UOV_intermediate_values_<parameter-set>_<PRG>.txt, 

where <PRG> is either AES or SHAKE.

There are 30 files in total: 15 parameter sets, each with two public-key-expansion options.

The parameter-set identifiers are as follows:

#####################################################
### Security level I
#####################################################
1v156m54l3q127
1v540m60l10q127
1v740m100l10q7 (Additional parameter set)
1v165m60l3q31 (Additional parameter set)
1v600m70l10q31 (Additional parameter set)

#####################################################
### Security level III
#####################################################
3v228m78l3q127
3v820m90l10q127
3v1100m140l10q7 (Additional parameter set)
3v246m87l3q31 (Additional parameter set)
3v890m100l10q31 (Additional parameter set)

#####################################################
### Security level V
#####################################################
5v306m105l3q127
5v1040m110l10q127
5v1490m190l10q7 (Additional parameter set)
5v324m114l3q31 (Additional parameter set)
5v1120m120l10q31 (Additional parameter set)


(B) Description of contents
(B-1) Parameters
This part describes the parameters of QR-UOV. (See also Section 2 of the specification.)
  - lambda : security parameter (128, 192, or 256)
  - q : prime power
  - l : degree of the irreducible polynomial f that defines the quotient ring GF(q)[x]/(f)
  - v : number of vinegar variables
  - m : number of oil variables
  - f : irreducible polynomial defining the quotient ring GF(q)[x]/(f)
  - W : invertible l-by-l matrix over GF(q) such that W Phi_f^g is symmetric for every g in GF(q)[x]/(f)
  - PRG : public-key-expansion option, either AES128 or SHAKE128. Private-key expansion always uses SHAKE256. (See also Subsection 4.8 of the specification.)

(B-2) Fixed Test Inputs
This part describes the fixed inputs used to generate the intermediate values for key generation, signature generation, and verification.
All values in this part and thereafter are expressed in hexadecimal unless otherwise noted.
  - seed_sk : seed for private key sk
  - message : message to be signed
  - salt rho : salt used in signature generation
               The value was selected to ensure that the linear system Lx = t − u is solvable (see Steps 16 and 18 of Algorithm 2 in the specification).
  - y_input : vector set in Algorithm 2 Step 3 of the specification

(B-3) KeyGen
This part presents seed_pk, S', and the public-key matrices; please refer to Sections (C) and (D) for the methods used to generate the matrices and for the notation of the matrices.
  - seed_pk : seed of public key pk generated from seed_sk (see Step 2 of Algorithm 1 in the specification).
  - S' : matrix generated from seed_sk (see Step 2 of Algorithm 1 in the specification).
  - Pi1 : sequence of matrices {P_{i,1} : i \in [1, m]} generated from seed_pk (see Step 4 of Algorithm 1 in the specification).
  - Pi2 : sequence of matrices {P_{i,2} : i \in [1, m]} generated from seed_pk (see Step 4 of Algorithm 1 in the specification).
  - Pi3 : sequence of matrices {P_{i,3} : i \in [1, m]} generated from Pi1, Pi2, and S' (see Step 5 of Algorithm 1 in the specification).

(B-4) Sign
This part presents the signatures and intermediate values generated from seed_pk, seed_sk, the message, and salt rho.
For the method to generate random numbers and the notation of vectors, please refer to Sections (C) and (D).
  - L : matrix (see Step 9 of Algorithm 2 in the specification).
  - u : vector (see Step 13 of Algorithm 2 in the specification).
  - t : vector generated from message and salt rho (see Step 17 of Algorithm 2 in the specification).
  - y_solution : vector (y_{v+1}, ...,y_n), which is one solution to the linear system Lx = t − u (see Step 19 of Algorithm 2 in the specification).
                 Free variables are set to fixed values (e.g. y_i = 1) rather than random values.
  - s : signature vector computed in Step 20 and canonicalized in Steps 21-23 of Algorithm 2 in the specification. Step 24 returns the signature sigma = (rho, s).

(B-5) Verify
This part presents the intermediate value used in signature verification.
Please refer to Section (D) for the notation of vectors.
  - t' : vector (see Step 15 of Algorithm 3 in the specification).


(C) Generation rules
We generated the intermediate values according to the following rules.
The following rules are provided to facilitate verification of the correctness of the procedures and are not optimized.

(C-1) Pseudorandom generators
Private-key expansion uses PRG_sk instantiated with SHAKE256, and public-key expansion uses PRG_pk instantiated with either SHAKE128 or AES128 as described in Subsection 4.8 of the specification.
The rejection-sampling input lengths are the tau values defined in Subsections 4.5 and 4.7 of the specification.

(C-2) Generation of finite field elements
The method to generate finite field elements is described in Subsections 4.6 and 4.7 of the specification.

(C-3) Generation of matrices
Expand_sk and Expand_pk are defined in Subsection 4.6 of the specification. Expand_sk generates S' and seed_pk from seed_sk, and Expand_pk generates Pi1 and Pi2 from seed_pk. Pi3 is then derived as specified in Step 5 of Algorithm 1 in the specification.

(C-4) Generation of vectors
A vector of GF(q) elements is generated by generating GF(q) elements (see (C-2)) and assigning them in order, starting with the first component.


(D) Notation rules
The intermediate values are expressed in hexadecimal notation according to this section.
The intermediate values in each file are presented in an easily verifiable notation for the purpose of facilitating verification of the correctness of the implementation.
Therefore, note that this is not an optimized representation and is redundant.
Please refer to Subsection 4.4 of the specification, Representation of Keys and Signature, for an efficient way to represent public keys, private keys, and signatures.

(D-1) Notation of matrices
(D-1-1) Matrices S', Pi1, Pi2, and Pi3 that are shown as the intermediate values consist of elements in GF(q^l).
All other matrices that are shown as the intermediate values consist of elements in GF(q).

(D-1-2) Each matrix is represented in hexadecimal as follows:
Each GF(q) element is represented in hexadecimal with ceil(log_16(q)) digits. Each GF(q^l) element is represented by its l coefficients over GF(q), in ascending order of degree, with each coefficient represented in the same way. The resulting hexadecimal strings are concatenated in row-major order.

(D-1-3) Pi1, which consists of m matrices, is represented by expressing all matrices in hexadecimal and concatenating them in order P_{1,1}, P_{2,1},...
Pi2 and Pi3 are represented in the same way.

For example, assuming q = 31, the hexadecimal representation of the following matrix whose elements are in GF(q) is as follows.

   [[15,  2,  6, 20],
    [ 2, 13, 20, 30],
    [ 0, 30, 29,  9],
    [30, 10,  9, 18]]
-->
   [[0f, 02, 06, 14],
    [02, 0d, 14, 1e],
    [00, 1e, 1d, 09],
    [1e, 0a, 09, 12]]
--> 0f|02|06|14|02|0d|14|1e|00|1e|1d|09|1e|0a|09|12
--> 0f020614020d141e001e1d091e0a0912

For example, assuming q = 7, the hexadecimal representation of the following matrix whose elements are in GF(q^l) is as follows.

  [[    2+2x  ,      x   ],
   [ 3+5x+2x^2, 3+5x+6x^2]]
-->
  [[ 2+2x+0x^2, 0+1x+0x^2],
   [ 3+5x+2x^2, 3+5x+6x^2]]
-->
  [[ 2,2,0,0,1,0 ],
   [ 3,5,2,3,5,6 ]]
--> 2|2|0|0|1|0|3|5|2|3|5|6
--> 220010352356

(D-2) Notation of vectors
All vectors that are shown as the intermediate values consist of elements in GF(q). All elements are represented in hexadecimal with ceil(log_16(q)) digits and concatenated in order starting from the first component.
